package com.zk.algorithm.array;

import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.bean.Interval;

import java.util.*;

/**
 * @author zk
 */
@LeetCode("56")
public class MergeIntervals {

    // [[1,3],[2,6],[8,10],[15,18]] => [[1,6],[8,10],[15,18]]
    // [[1,4],[4,5]] => [[1,5]]
    //
    public List<Interval> merge(List<Interval> intervals) {
        // 先排序
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval obj0, Interval obj1) {
                return obj0.start - obj1.start; // 负数代表升序
            }
        });

        List<Interval> result = new ArrayList<>();

        Interval prev = null;
        for (Interval inter : intervals) {
            //
            // 当前需要判定的区间的 start 不位于上一个区间的 end 的里面，添加进来
            // [__________]
            //            ↑
            //        pre.end
            //                     [_________]
            //                     ↑
            //                inter.start
            //
            if (prev == null || inter.start > prev.end) {
                result.add(inter);
                prev = inter;
            } else if (inter.end > prev.end) {

                // 否则，就肯定在里面。然后再修改 end
                // [__________]_ _ _ _ _ _ _ _]
                //            ↑
                //        pre.end
                //       [____________________]
                //                            ↑
                //                       inter.end
                //

                // Modify the element already in list
                prev.end = inter.end;
            }
        }

        return result;
    }

    public static void main(String...args) {
        System.out.println(new MergeIntervals().merge(Arrays.asList(new Interval(2, 6), new Interval(8, 10), new Interval(1,3), new Interval(15, 18))));
        System.out.println(new MergeIntervals().merge(Arrays.asList(new Interval(1, 4), new Interval(4, 5))));
    }

}
